1. Technical Field
Embodiments of the present invention relate generally to data prefetching, and more specifically, to data prefetching during program runtime even though memory access appears irregular when statically analyzed at compile time.
2. Discussion of the Related Art
A gap in the performance speeds of microprocessors and Dynamic Random Access Memory (DRAM) devices has necessitated the use of aggressive techniques that are designed to either reduce or completely hide the latency of main memory accesses. Large cache hierarchies have reduced this latency for the most frequently accessed data, but scientific programs still may spend half of their run times stalled on memory requests. Data access stalls are a major performance-limiting factor in many software applications. Data prefetching is utilized to improve performance in such software applications by hiding the memory latency. Instead of waiting for a cache miss to initiate a memory fetch, data prefetching anticipates such misses and issues a fetch to the memory system in advance of the actual memory reference.
Data prefetching may be accomplished when the data addresses for specific memory loads may be predicted in advance by a computer program product, such as a compiler. Data addresses for specific memory loads may be predicted in advance specifically in scientific applications where regular data access patterns occur due to the use of data structures such as arrays. However, if the data accesses appear to be irregular, at least statically, i.e., during compile time, the compiler may not be able to predict addresses in advance.